export const getInputs = () => [
	[[5, 7, 7, 8, 8, 10], 8],
	[[5, 7, 7, 8, 8, 10], 6],
	[[], 0],
	[[1], 1],
];

/**
 * [**34. 在排序数组中查找元素的第一个和最后一个位置**](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)
 *
 * 给你一个按照非递减顺序排列的整数数组 `nums`，和一个目标值 `target`。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 `target`，返回 `[-1, -1]`。
 * 你必须设计并实现时间复杂度为 `O(log n)` 的算法解决此问题。
 *
 * 1. **示例 1：**
 * ```
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * ```
 *
 * 2. **示例 2：**
 * ```
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * ```
 *
 * 3. **示例 3：**
 * ```
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * ```
 *
 * @param nums
 * @param target
 */
export default function (nums: number[], target: number): number[] {
	const binSearch = (rangeMin: number, rangeMax: number): number => {
		if (rangeMax - rangeMin <= 1) return nums[rangeMin] === target ? rangeMin : -1;

		const midIndex = Math.floor((rangeMax + rangeMin) / 2);
		const midValue = nums[midIndex];

		if (midValue < target) return binSearch(midIndex, rangeMax);
		if (midValue > target) return binSearch(rangeMin, midIndex);
		return midIndex;
	};

	const index = binSearch(0, nums.length);
	if (index === -1) return [-1, -1];

	let pre = index,
		suf = index;
	while (nums[--pre] === target);
	while (nums[++suf] === target);

	return [pre + 1, suf - 1];
}
